package com.frx.leetoffer.dayone;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IDEA
 * @description 重建二叉树
 *              preorder : 3 9 20 15 7
 *              inorder : 9 3 15 20 7
 *
 *             output : 9 <- 3 -> 20
 *                               /  \
 *                              15   7
 * @author: xrf
 * @Date: 2019/5/8
 * @Time: 14:27
 */
public class RebuildBST {

    // 缓存中序遍历数组每个值对应的索引
    private Map<Integer,Integer> indexForInOrders = new HashMap<>();

    public static void main(String[] args){

    }

    /**
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre,int[] in){
        for (int i=0;i<in.length;i++){
            indexForInOrders.put(in[i],i);
        }
        return reConstructBinaryTree(pre,0,pre.length-1,0);
    }


    private TreeNode reConstructBinaryTree(int[] pre,int preL,int preR,int inL){

        if (preL > preR){
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        int inIndex = indexForInOrders.get(root.val);
        int leftTreeSize = inIndex - inL;
        root.left = reConstructBinaryTree(pre,preL+1,preL+leftTreeSize,inL);
        root.right = reConstructBinaryTree(pre,preL + leftTreeSize+1,preR,inL+leftTreeSize+1);

        return root;
    }

    private static class TreeNode{
        int val;
        TreeNode left, right;

        public TreeNode(int val){
            this.val = val;
        }
    }
}
